/** @file ast.c
* Implements all AST functions defined in ast.h .
* @author Victor Petrov <victor_petrov@harvard.edu>
* @date   Feb 26, 2011
* @cond
*------------------------------------------------------------------------------
* LEGAL:
*------------------------------------------------------------------------------
*
* Copyright (c) 2011, The President and Fellows of Harvard College
* Copyright (c) 2011, The Neuroinformatics Research Group at Harvard University
* All rights reserved.
*
* License: New BSD License   <http://creativecommons.org/licenses/BSD/>
*-------------------------
* Redistribution and use in source and binary forms, with or without 
* modification, are permitted provided that the following conditions are met:
*
*	Redistributions of source code must retain the above copyright notice, 
*	this list of conditions and the following disclaimer.
*
*	Redistributions in binary form must reproduce the above copyright notice, 
*	this list of conditions and the following disclaimer in the documentation
*	and/or other materials provided with the distribution.
*
*	Neither the name of the Neuroinformatics Research Group at Harvard, nor 
*	the names of its contributors may be used to endorse or promote products 
*	derived from this software without specific prior written permission.
*
* THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS "AS IS" 
* AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE 
* IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE 
* ARE DISCLAIMED. IN NO EVENT SHALL THE COPYRIGHT HOLDER OR CONTRIBUTORS BE 
* LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR 
* CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF 
* SUBSTITUTE GOODS OR SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS 
* INTERRUPTION) HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN 
* CONTRACT, STRICT LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) 
* ARISING IN ANY WAY OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE 
* POSSIBILITY OF SUCH DAMAGE.
*------------------------------------------------------------------------------
* vim: ts=4
*------------------------------------------------------------------------------
* @endcond
*/

/* PHP extension include files*/
#ifdef PHPEXT
	#include "php.h"
	#include "php_vxp.h"
#endif

/* Regular include files */
#include <assert.h>           	/* assert() */
#include <stdarg.h>				/* va_list, va_start(), va_end() */

#include "ast.h"				/* struct Node, function declarations */
#include "errors.h"				/* memerror() */
#include "nonterminalnames.h"	/* NonTerminalNames[] */

/** Creates a NODE_TOKEN node.
* @param[in] mem   MemBlockInfo struct handling all memory operations
* @param[in] token The token the new node will represent
* @param[in] name  The name of the token
* @return A pointer to a new Node
*/
struct Node* newToken(struct MemBlockInfo* mem, enum yytokentype token, 
                      const char* const name)
{
    struct Node* n=NULL;	/* the new node */

	n=memGet(mem);			/* allocate a new node */
    n->type=NODE_TOKEN;		/* set node properties */
    n->data.t=token;
    n->name=name;

    return n;				/* and voila! */
}

/** Creates a NODE_RULE node with, optionally, its child Nodes.
* @param[in] mem       MemBlockInfo struct handling all memory operations
* @param[in] rule      The rule the new node will represent
* @param[in] children  The number of children for the new node
* @param[in] ...       The children (struct Node*)
* @return A pointer to a new Node
*/
struct Node* newRule(struct MemBlockInfo* mem, enum NonTerminals rule, 
                     unsigned int children, ...)
{
    struct Node* n=NULL;                        /* the new node */
	struct Node* child=NULL;                    /* a child node */
	va_list args;                               /* va_list for child nodes */
	int i=0;

    assert(mem);                                /* no NULL values please */

	n=memGet(mem);                              /* allocate a new node */
    n->type=NODE_RULE;                          /* set node properties */
	n->name=NonTerminalNames[rule];
    n->data.nt=rule;

	if (children>0)                             /* if there are children */
	{
		/* Add the children */
		va_start(args,children);                /* start the var args */

		for (i=0;i<children;++i)                /* iterate over all children */
		{
			child=va_arg(args,struct Node*);    /* get next child node */
			nodeAppendChild(mem, n,child);      /* append child node */
		}

		va_end(args);                           /* done */
	}

    return n;                                   /* here's the new node! */
}

/** Creates a new NODE_STRING node that represents an NCName value 
* @param[in] mem    MemBlockInfo struct handling all memory operations
* @param[in] value  The string value
* @return A pointer to a new Node
* @warning Caller must make sure value is valid
*/
struct Node* newNCName(struct MemBlockInfo* mem, char* value)
{
    struct Node* n=NULL;    /* the new node */

    assert(mem);            /* no NULL values please */
    assert(value);          

    n=memGet(mem);          /* allocate a new node */
    n->type=NODE_STRING;    /* set node properties */
    n->name="NCName";
    n->data.p=value;        /* char data is NOT duplicated */

    return n;               /* return the new node */
}

/** Creates a new NODE_STRING node that represents a Literal value 
* @param[in] mem    MemBlockInfo struct handling all memory operations
* @param[in] value  The string value
* @return A pointer to a new Node
* @warning Caller must make sure @c value is valid
*/
struct Node* newLiteral(struct MemBlockInfo* mem, char* value, 
                        enum QuoteType quotes)
{
    struct Node* n=NULL;    /* the new node */

    assert(mem);            /* no NULL values please */
    assert(value);

    n=memGet(mem);          /* allocate a new node */
    n->type=NODE_STRING;    /* set node properties */
    n->name="Literal";
    n->data.p=value;
    n->extra.quotes=quotes;

    return n;               /* return the new node */
}

/** Appends a Node child to a node.
* @param[in] mem    MemBlockInfo struct handling all memory operations
* @param[in] node   The parent node
* @param[in] child  The child node
*/
void nodeAppendChild(struct MemBlockInfo* mem, struct Node* node, 
                     struct Node* child)
{
    assert(mem);                                /* No NULL values, please */
	assert(node);
	assert(child);

    if (child->parent)                          /* internal checks */
        nodeerror("already has a parent:", child,child->parent, mem);

	if (node->children)                         /* are there other children? */
		nodeInsertRight(mem, node->last,child); /* if yes, append child */
	else
	{
		node->first=child;                      /* make sure the parent's */
		node->last=child;                       /* properties are updated */

		nodeReparent(child,node);               /* change parents */
		++node->children;                       /* increment child count */
	}
}

/** Appends multiple Node siblings to another Node
* @param[in] mem      MemBlockInfo struct handling all memory operations
* @param[in] node     The node to append siblings to
* @param[in] siblings Number of sibling nodes to append
* @param[in] ...      The siblings (struct Node*)
*/
void nodeAppendSiblings(struct MemBlockInfo* mem, struct Node* node, 
                        unsigned int siblings, ... )
{
    struct Node* last=NULL;                 /* the current last sibling */
    struct Node* sibling=NULL;              /* one new sibling */
    va_list args;                           /* list of new sibling args */
    int i=0;

    assert(mem);                            /* no NULL values please */
    assert(node);
    
    if (siblings==0)                        /* No siblings? kthxbye */
        return;

    last=nodeGetLastSibling(node);          /* always append to last node */
    va_start(args,siblings);                /* start arg list */

    for (i=0;i<siblings;++i)                /* iterate over all new nodes */
    {
        sibling=va_arg(args,struct Node*);  /* get one new sibling */
        nodeInsertRight(mem, last,sibling); /* append the sibling */
        last=sibling;                       /* this node is now last */
    }

    va_end(args);                           /* done */
}

/** Inserts a node (and all its siblings) as a direct sibling of @c node
* @param[in] node     The reference node
* @param[in] sibling  The new sibling
* @param[in] mem      MemBlockInfo struct handling all memory operations
* @warning @c sibling must not already have a parent and should not already
*          be a sibling of @c node
*/
void nodeInsertRight(struct MemBlockInfo* mem, struct Node* node,
                     struct Node* sibling)
{
	struct Node* start=NULL;                /* first sibling (of sibling arg)*/
	struct Node* end=NULL;                  /* last sibling (of sibling arg) */

	assert(node);                           /* no NULL values please */
	assert(sibling);
    assert(mem);

    if (sibling->parent)                    /* internal parent check */
        nodeerror("already has a parent:",sibling,sibling->parent, mem);
    
    if (nodeHasSibling(node,sibling))       /* internal sibling check */
        nodeerror("is already a sibling of",sibling,node, mem);

	start=nodeGetFirstSibling(sibling);     /* get the first node to append */
	end=nodeGetLastSibling(sibling);        /* get the last node to append */

	if (node->right)                        /* does this node have a sibling?*/
	{
		end->right=node->right;             /* if yes, insert all siblings */
		end->right->left=end;               /* to the left of the old sibling*/
	}

	start->left=node;                       /* left sibling */
	node->right=start;                      /* new right sibling of node */

	if (node->parent)                       /* does the node have a parent? */
	{
		node->parent->children=nodeCountSiblings(sibling)+1; /* child count */
		nodeReparent(sibling,node->parent); /* set new parent of new sibling */
	}
	else
		nodeReparent(sibling,NULL);         /* set no parent for new sibling */
}

/** Changes the parent of a node and all its siblings.
* @param[in] child   The child node
* @param[in] parent  The new parent
* @warning @c parent is allowed to be NULL
*/
void nodeReparent(struct Node* child, struct Node* parent)
{
	struct Node* start=NULL;            /* the first sibling of child */
	struct Node* end=NULL;              /* the last sibling of child */
    struct Node* node=NULL;             /* the current node */

	assert(child);                      /* child cannot be NULL */

	start=nodeGetFirstSibling(child);   /* the first sibling of child */
	end=nodeGetLastSibling(child);      /* the last sibling of child */

	node=start;                         /* start with the first sibling */
	while (node)                        /* loop over all siblings */
	{
		node->parent=parent;            /* assign new parent */
		node=node->right;               /* move to the next sibling */
	}

    if (parent)                         /* update the parent */
    {
        parent->first=start;            /* set the first child */
        parent->last=end;               /* set the end child */
    }
}

/** Retrieves the first sibling of a node
* @param[in] child  The node
* return The first sibling of @c child
*/
struct Node* nodeGetFirstSibling(struct Node* child)
{
	while (child)               /* loop over all siblings */
	{
		if (child->left)        /* has previous sibling? */
			child=child->left;  /* move to the new sibling */
		else
			break;              /* otherwise, end the loop */
	}

    return child;               /* return the result */
}

/** Retrieves the last sibling of a node
* @param[in] child  The node
* return The last sibling of @c child
*/
struct Node* nodeGetLastSibling(struct Node* child)
{
	while (child)               /* loop over all siblings */
	{
		if (child->right)       /* has next sibling ? */
			child=child->right; /* move to the new sibling */
		else
			break;              /* otherwise, end the loop */
	}

	return child;               /* return the result */
}

/** Counts the number of siblings from the left and from the right
* @param[in] node The node who's siblings need to be counted
* @result Number of siblings found
*/
unsigned int nodeCountSiblings(struct Node* node)
{
	struct Node* first=NULL;        /* first sibling */
	struct Node* last=NULL;         /* last siblings */
	unsigned int count=0;           /* result */

	assert(node);                   /* node cannot be NULL */

	first=nodeGetFirstSibling(node);/* find the first sibling */
	last=nodeGetLastSibling(node);  /* find the last sibling */

	while (first!=last)             /* loop over all siblings */
	{
		first=first->right;         /* move to the next sibling */
		++count;                    /* increment counter */
	}

	return count;                   /* return the result */
}

/** Checks whether a @c node has a specific @c sibling
* @param[in] node The node who's siblings need to be counted
* @param[in] sibling  The sibling to search for
* @result @c 1 on Success, @c 0 on Failure
*/
int nodeHasSibling(struct Node* node, struct Node* sibling)
{
    struct Node* first=NULL;            /* first sibling of node */

    first=nodeGetFirstSibling(node);    /* get the first sibling */

    while (first)                       /* loop over all siblings */
    {
        if (first==sibling)             /* compare Node's */
            return 1;                   /* return 1 on success */

        first=first->right;             /* move to the next sibling */
    }

    return 0;                           /* return 0 on failure */
}

/** Check if @c node is a rule of type specified by @c rule
* @param[in] node  The node to check
* @param[in] rule  The rule to check against
* @return @c 1 on Success, @c 0 on Failure
*/
int isRule(const struct Node* node, enum NonTerminals rule)
{
    /* Make sure this node holds the correct rule*/
    if (!node || (node->type!=NODE_RULE) || (node->data.nt!=rule))
        return 0;

    /* otherwise, */
    return 1;
}

/** Checks whether a @c node contains a @c rule as a child
* @param[in] node  The node to check
* @param[in] rule  The rule to check against
* @return @c 1 on Success, @c 0 on Failure
*/
int hasRule(const struct Node* node, enum NonTerminals rule)
{
    node=node->first;           /* first child */

    while (node)                /* loop over all children */
    {
        if (isRule(node,rule))  /* does this child match the rule? */
            return 1;           /* if yes, return 1 */

        node=node->right;       /* otherwise, check the next child */
    }

    return 0;                   /* if not found, return 0 */
}


/** Check if @c node is a token of type specified by @c token
* @param[in] node   The node to check
* @param[in] token  The token to check against
* @return @c 1 on Success, @c 0 on Failure
*/
int isToken(const struct Node* node, enum yytokentype token)
{
    /* Make this node holds the correct token type */
    if (!node || (node->type!=NODE_TOKEN) || (node->data.t!=token))
        return 0;

    /* on success */
    return 1;
}

/** Checks whether a @c node contains a @c token as a child
* @param[in] node   The node to check
* @param[in] token  The token to check against
* @return @c 1 on Success, @c 0 on Failure
*/
int hasToken(const struct Node* node, enum yytokentype token)
{
    node=node->first;               /* first child */

    while (node)                    /* loop over all children */
    {
        if (isToken(node,token))    /* if found */
            return 1;

        node=node->right;           /* otherwise, continue */
    }

    return 0;                       /* on failure, return 0 */
}

